import java.util.HashMap;

//最小覆盖字串
//测试链接 https://leetcode.cn/problems/minimum-window-substring/description/
public class MinWindow {
    public String minWindow(String s, String t) {
        HashMap<Character,Integer> target = new HashMap<>(); //存放t字符串每个元素的个数
        for(int i = 0; i < t.length(); i++){
            char in = t.charAt(i);
            target.put(in, target.getOrDefault(in,0)+1);
        }

        HashMap<Character,Integer> cur = new HashMap<>();
        int len = Integer.MAX_VALUE;
        int start = 0; //开始位置
        int cnt = 0; //标记有效字符
        for(int left = 0, right = 0; right < s.length(); right++){
            //进窗口
            char in = s.charAt(right);
            cur.put(in, cur.getOrDefault(in,0)+1);
            if(cur.get(in) <= target.getOrDefault(in,0) ){
                cnt++;
            }

            //判断
            while(cnt >= t.length() ){

                if(right - left + 1 < len){   //标记最短长度，和开始位置
                    len = right - left + 1;
                    start = left;
                }
                //出窗口
                char out = s.charAt(left);
                cur.put(out, cur.get(out) - 1);

                if(cur. get(out) < target.getOrDefault(out,0)){
                    cnt--;
                }

                if(cur.get(out) == 0){
                    cur.remove(out);
                }
                left++;
            }
        }
        //构造结构
        if(len == Integer.MAX_VALUE){
            return "";
        }

        String ret = s.substring(start,start+len);
        return ret;
    }
}
